Теорема о линейном порядке

Произвольное отношение порядка $\preceq$ на произвольном множестве $A$ можно дополнить до отношения линейного порядка на $A$.

**Доказательство для конечных множеств**: алгоритм топологической сортировки * рассмотрим диаграмму Хассе ЧУМа $(A, \preceq)$ как орграф * возьмем любой минимальный элемент (исток в орграфе), присвоим ему номер 1 и удалим из орграфа * продолжим процедуру в цикле, присваивая наименьший незанятый номер любому истоку оставшегося орграфа * нумерация вершин задает линейный порядок, содержащий исходный $\square$